package com.ma.dp.a01;

/**
 * @ClassName Solution887
 * @Author: mayongqiang
 * @DATE 2022/4/15 16:16
 * @Description: 扔鸡蛋问题
 */
/* 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
 *
 * 已知存在楼层 f ，满足0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
 *
 * 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。
 * 如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
 *
 * 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
 */
/*
    每一层楼都扔一下
    for i in range(N):

 */
public class Solution887 {
    public static void main(String[] args) {
        System.out.println(superEggDrop01(3, 14));
        System.out.println(superEggDrop(3, 14));
    }

    /* 方法二、dp[k][m] = n 代表 k个鸡蛋 扔m次 最坏情况下最多测试n层楼
        eg:dp[1][7] = 7 代表 1个鸡蛋 扔7次 这个状态下最多给你7层楼使得确定楼层并且使得鸡蛋刚好不碎
    */
    static int superEggDrop01(int k, int n) {
        int m = 0;
        int[][] dp = new int[k + 1][n + 1];
        while (dp[k][m] < n) {
            m++;
            // 状态转移
            for (int i = 1; i <= k; i++) {
                dp[i][m] = dp[i][m - 1] + dp[i - 1][m - 1] + 1;
            }
        }
        return m;
    }


    /* 方法一、dp[k][n] = x 代表 k个鸡蛋n层楼最坏情况下最少扔鸡蛋数
              这种情况下,需要穷举所有的扔法可能
    */
    // 定义子问题 k个鸡蛋,N层楼 确定最小操作数
    static int[][] memo;

    public static int superEggDrop(int k, int n) {
        // 枚举所有楼层  for i in range(n):
        // 最坏的情况 对于某一层 i  碎/不碎 里面取最大
        // 至少  所有楼层的情况取最小
        // 有dp(k,n) = 1+minx[ max(dp(k,n-x),dp(k-1,x-1)) ]
        memo = new int[k + 1][n + 1];
        return dp(k, n);

    }

    static int dp(int k, int n) {
        if (k == 1) {
            return n;
        }
        if (k == 0 || n == 0) {
            return 0;
        }
        if (memo[k][n] != 0) {
            return memo[k][n];
        }
        int res = Integer.MAX_VALUE;
        // 从i=1到n顺序找
        //for (int i = 1; i <= n; i++) {
        //    res = Math.min(1 + Math.max(dp(k, n - i), dp(k - 1, i - 1)), res);
        //}

        // 二分找
        int lo = 1, hi = n;
        while (lo <= hi) {
            // i = mid  选择在mid楼扔
            int mid = (lo + hi) / 2;
            int broken = dp(k - 1, mid - 1);
            int not_broken = dp(k, n - mid);
            if (broken > not_broken) {
                hi = mid - 1;
                res = Math.min(res, broken + 1);
            } else {
                lo = mid + 1;
                res = Math.min(res, not_broken + 1);
            }
        }

        memo[k][n] = res;
        return memo[k][n];
    }
}
